#!/usr/bin/env python3
# -*- coding: utf-8 -*-

# 1.冒泡排序
def bubble_sort(arr):
    length = len(arr)
    for i in range(length-1):  # 外层循环的次数是遍历的轮数，比如十个元素，只需要遍历九次就好了，所以范围为length-1
        for j in range(length-1-i): # 内层循环的轮数是每次遍历和多少个数进行比较，每遍历一次，就会有一个数有序，少一个无序，故需要减去i
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

# 2.快速排序
def quickSort(list, start, end):  # start,end 是指指针
    i, j = start, end
    if start < end:
        base = list[i]  # 设置基准数为i,即为start
        while i < j:
            if list[j] >= base:  # 找到比基准数小的数字
                j -= 1  # 将炮兵j向左移动
            list[i] = list[j]  # 将找到的j复制给i
            # 同样的方法执行前半区域
            if list[i] <= base:
                i += 1
            list[j] = list[i]
        list[i] = base  # i=j,即将这个数设置为base

        quickSort(list, start, i - 1)
        quickSort(list, j + 1, end)
    return list

if __name__ == '__main__':
    x = [9,5,2,1,10,6,7]
    print(bubble_sort(x))
    print(quickSort(x,9,7))


